1. Field of the Invention
The present invention relates to location estimation, and more specifically to estimating the location of both stationary and moving objects in a wireless environment.
2. Description of the Related Art
With the development of pervasive computing and location-aware systems and services, there has been an increased interest in location estimation techniques for both outdoor and indoor object positioning. Because of the poor indoor coverage of the Global Positioning System (GPS), there is a greater interest in indoor location estimation.
One conventional approach to indoor location estimation deploys a dedicated sensor network using, for example, infrared or ultrasound technologies. But this approach has cost and maintenance problems.
Another conventional approach is radio frequency (RF) based static scene analysis. With the existing wireless LAN infrastructure, the RF-based static scene analysis system collects radio signal information from wireless LAN beacons, creates a static location information database that stores the collected radio signal information, and obtains location estimates based on radio wave characteristics.
Static scene analysis collectively refers to location estimation techniques involving measurement, calibration and analysis of a specific metric that can be obtained from sensor reading. Static scene analysis typically consists of an off-line stage, where calibration of the indoor wireless environment is carried out, and an on-line (or runtime) stage, where the calibration is used for location estimation.
Specifically, during the off-line stage, a site survey obtaining RF-characteristics at numerous known locations of a wireless environment takes place first. This typically involves receiving signal strength measurements from multiple access points, such as a received signal strength indicator (RSSI) metric, or a link quality metric. The information collected during the site survey is processed and stored in a location information database. The calibration of the wireless environment is then finished, and the information stored will be compared with inputs acquired during the runtime.
During the on-line (or runtime) stage, a user provides a run-time input that is measured instantly at the location of interest. The user uses the same metric that has been used in the off-line stage. Then a location estimation algorithm, which will be introduced below, is applied to compare the run-time and the off-line measurements and compute the location of the object. In RF-signal measurement, numerous sources of interference and noise, such as fading, blocking, and shadowing, occur both transiently and over significant period of time. These phenomena cause corrupted run-time inputs and introduce location estimate errors.
Three conventional algorithms that are widely used in RF-based static scene analysis, i.e., triangulation, K-nearest neighbor averaging, and smallest M-polygon are described in detail below.
FIG. 1 illustrates the triangulation algorithm for location estimation. The triangulation computes the location estimate by solving systems of quadratic equations. The triangulation forms circles whose centers are the locations of the transmitters, e.g., access points or base stations. In FIG. 1, the locations and RF characteristics of access points 1, 2, and 3 have been obtained at numerous known locations, which are used for off-line calibration, during the off-line stage described above. Distances d1 between the object and the access point 1, d2 between the object and the access point 2, and d3 between the object and the access point 3 are calculated based on radio wave characteristics, e.g., TOA or TDOA. Triangulation forms sets of circles. Each of the reference points, access points 1, 2 or 3, becomes the center of a circle, and the distances between the object and the center, d1, d2 or d3, becomes the radius of that circle.
Triangulation estimates locations based on various intersection areas formed by these circles. If three formed circles meet at a single spot, that spot becomes the location estimate as a result of the triangulation. However, as a practical matter, the three circles rarely will meet at a single spot. More often, if the circles intersect, they will intersect in multiple spots. In FIG. 1, the three circles have six intersection points, P1, P2, P3, P4, P5 and P6. The triangulation algorithm examines areas formed by the intersection points to obtain a location estimate for the object. Specifically, the triangle formed by P2, P4 and P5 has the smallest area among all possible triangles formed by these intersection points, and the centroid X of the triangle (P2, P4, P5) is the best location estimate of the object.
FIG. 2 illustrates the K-nearest neighbor averaging algorithm for location estimate, wherein K=5. Typically, K is larger than 2. Experimental analysis shows that K=3 gives the best performance. Let a triplet (Sa, Sb, Sc) represent a set of run-time signal strength measurements at a location of interest from three base stations a, b, and c. Five triplets which have the least root mean square (RMS) error in signal strength between the run-time and the off-line measurements are found. The root mean square error in signal strength is calculated as follows:rms=√{square root over ((a−ai)2+(b−bi)2+(c−ci)2)}{square root over ((a−ai)2+(b−bi)2+(c−ci)2)}{square root over ((a−ai)2+(b−bi)2+(c−ci)2)}  (1)
wherein (Sa, Sb, Sc) represents off-line signal strength measurements at the location of interest.
In particular, these five triplets are: signal strength triplet (a1, b1, c1) at position L1 (x1, y1) from base stations a, b and c; signal strength triplet (a2, b2, c2) at position L2 (x2, y2) from base stations a, b and c; . . . and signal strength triplet (a5, b5, c5) at position L5 (x5, y5) from base stations a, b and c. L1, . . . , L5 are determined by using the location information database. The location information database for RF-based static scene analysis typically contains entries used to map RF signal metrics to positions (i.e., transfer from signal domain to space domain). The positions of these five locations are averaged to yield the location estimate of the object as follows:L=(L1+L2+L3+L4+L5)/5  (2)
FIG. 3 illustrates the smallest M-polygon algorithm for location estimate, wherein M=3. M is the number of access points, or base stations, used for the system. M=3 gives reasonably good performance for the algorithm. Three base stations A, B, and C provides separate candidate locations A1, A2, B1, B2, C1 and C2 that match best with the off-line measurements. The algorithm then searches for the polygon that has the smallest perimeter formed by candidate locations contributed by each reference base station, wherein one and only one candidate from each base station must constitute a vertex of the polygon. In FIG. 3, candidate locations A1, B2 and C2 form the smallest perimeter polygon, in this case, a triangle. The final location estimate of the object is the centroid X of the polygon:x=(A1+B2+C2)/3  (3)
The conventional static scene analysis maps from the radio signal domain to the space domain. The final estimate is typically within a coordinate system. A main drawback of the static scene analysis is that it cannot effectively cope with the impact of errors in the radio signal domain. Due to interference and noise, objects at different locations might be represented similarly in the radio signal domain, a phenomenon called aliasing. The conventional methods can not detect aliasing, and may provide these different locations with similar location estimates.
A selective fusion location estimation (SELFLOC) algorithm selectively combines or fuses multiple location information sources to yield a combined estimate in a theoretically optimal manner. The SELFLOC algorithm is disclosed in U.S. patent application Ser. No. 10/330,523, filed Dec. 27, 2002, which is incorporated herein by reference.
FIG. 4 illustrates an overview of the SELFLOC algorithm to fuse three information sources 1, 2 and 3. Each input branch is individually weighted by one of the weights 1, 2, and 3. The sum of the weighted input branches provides the SELFLOC estimate.
The branch weights 1, 2 and 3 are calibrated during the off-line stage using error feedback. A minimum mean square error (MMSE) algorithm can be used for SELFLOC weight training and calibration. As shown in FIG. 4, three location estimates available independently are to be fused, and x-coordinates of these estimates are X1, X2 and X3. The weights for these input branches are w1, w2, and W3 respectively. Thus, the SELFLOC estimate X could be written as:X=w1·X1+w2·X2+w3·X3  (4)
It would be advantageous to provide a method for more accurate processing of collected signals to estimate locations of stationary and mobile objects with improved accuracy.